package oxing.util;

import java.util.Iterator;

public final class HashSet<E> implements Set<E>, Iterable<E> {
	final static class Entry<E> {
		int hash;
		E element;

		Entry<E> next;

		public Entry(int hash, E element, Entry<E> next) {
			this.hash = hash;
			this.element = element;
			this.next = next;
		}
	}

	final static int DEFAULT_INITIAL_CAPACITY = 1 << 4;
	final static int MAXIMUM_CAPACITY = 1 << 30;
	final static Entry<?>[] EMPTY_TABLE = {};
	@SuppressWarnings("unchecked")
	Entry<E>[] table = (Entry<E>[]) EMPTY_TABLE;
	int threshold;
	int size;

	public HashSet(int capacity) {
		if (capacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + threshold);
		threshold = capacity >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
				: (capacity > 1) ? Integer.highestOneBit((capacity - 1) << 1) : 1;
	}

	@SuppressWarnings("unchecked")
	private Entry<E>[] inflateTable(int capacity) {
		threshold = (int) Math.min(capacity * 0.75f, MAXIMUM_CAPACITY + 1);
		return table = new Entry[capacity];
	}

	public E get(E e) {
		if (size == 0)
			return null;
		Entry<E> entry;
		int hash, index;
		index = null == e ? (hash = 0) : ((hash = hash(e)) & (table.length - 1));
		entry = getEntry(hash, e, index);
		return null == entry ? null : entry.element;
	}

	public boolean contains(E e) {
		if (size == 0)
			return false;
		Entry<E> entry;
		int hash, index;
		index = null == e ? (hash = 0) : ((hash = hash(e)) & (table.length - 1));
		entry = getEntry(hash, e, index);
		return null == entry;
	}

	public E put(E e) {
		if (table == EMPTY_TABLE)
			inflateTable(threshold);
		Entry<E> entry;
		int hash, index;
		index = null == e ? (hash = 0) : ((hash = hash(e)) & (table.length - 1));
		entry = getEntry(hash, e, index);
		if (null == entry) {
			entry = addEntry(hash, e, index);
		}
		return entry.element;
	}

	public E remove(E e) {
		if (size == 0)
			return null;
		Entry<E> entry;
		int hash, index;
		index = null == e ? (hash = 0) : ((hash = hash(e)) & (table.length - 1));
		entry = removeEntry(hash, e, index);
		return null == entry ? null : entry.element;
	}

	public int size() {
		return size;
	}

	public void clear() {
		final Entry<E>[] arrays = this.table;
		final int length = arrays.length;
		for (int i = 0; i < length; i++)
			arrays[i] = null;
		size = 0;
	}

	private Entry<E> getEntry(final int hash, final E element, final int index) {
		for (Entry<E> e = table[index]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.element) == element || (element != null && element.equals(k))))
				return e;
		}
		return null;
	}

	private Entry<E> addEntry(final int hash, final E e, int index) {
		if ((size >= threshold) && (null != table[index])) {
			resize(table.length << 1);
			index = hash & (table.length - 1);
		}
		size++;
		return table[index] = new Entry<E>(hash, e, table[index]);
	}

	private Entry<E> removeEntry(final int hash, final E element, final int index) {
		if (table[index] == null)
			return null;
		Entry<E> e = table[index];
		Object k;
		if (e.hash == hash && ((k = e.element) == element || (element != null && element.equals(k)))) {
			size--;
			table[index] = e.next;
			return e;
		}
		for (Entry<E> e2 = e.next; e2 != null; e2 = (e = e2).next) {
			if (e2.hash == hash && ((k = e2.element) == element || (element != null && element.equals(k)))) {
				size--;
				e.next = e2.next;
				return e2;
			}
		}
		return null;
	}

	private void resize(int newCapacity) {
		final Entry<E>[] oldTable = table;
		final int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}
		final Entry<E>[] newTable = inflateTable(newCapacity);
		Entry<E> entry, next;
		int index;
		for (int i = 0; i < oldCapacity; i++) {
			entry = oldTable[i];
			while (null != entry) {
				next = entry.next;
				index = entry.hash & (newCapacity - 1);
				entry.next = newTable[index];
				newTable[index] = entry;
				entry = next;
			}
		}
	}

	private int hash(Object k) {
		int h = k.hashCode();
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	public Iterator<E> iterator() {
		return null;
	}

	final static class HashIterator<E> implements Iterator<E> {
		final Entry<E>[] arrays;
		int index;
		final int length;
		Entry<E> entry;

		public HashIterator(Entry<E>[] arrays) {
			this.length = (this.arrays = arrays).length;
			entry = arrays[index = 0];
		}

		public boolean hasNext() {
			for (; entry == null && index < length; index++)
				entry = arrays[index];
			return entry != null;
		}

		public E next() {
			Entry<E> e;
			for (; entry == null && index < length; index++)
				entry = arrays[index];
			if (entry == null)
				return null;
			entry = (e = entry).next;
			return e.element;
		}

		public void remove() {
			throw new IteratorException("Does not support remove();");
		}
	}
}
